﻿#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include"test.h"
using namespace std;



//int main()
//{
//	vector<int> v;
//	cout << v.size();
//	v.reserve(5);
//	cout << v.size();
//	//v[2] = 1;
//	for (int i = 0; i < v.size(); i++)
//	{
//		cout << v[i];
//	}
//	return 0;
//}
////void remove_space(string& s)
////{
////    int cur = 0;
////    int dest = 0;
////    while (cur < s.size())
////    {
////        if (s[cur] == ' ')
////        {
////            cur++;
////        }
////        else
////        {
////            while (cur < s.size() && s[cur] != ' ')
////            {
////                s[dest++] = s[cur++];
////            }
////            if (dest < s.size())
////            {
////                s[dest++] = ' ';
////            }
////        }
////    }
////    s.resize(dest);
////}
////void remove_space(string& s)
////{
////    int slow = 0;
////    int i = 0;
////    while (i < s.size())
////    {
////        if (s[i] == ' ')
////        {
////            i++;
////        }
////        else
////        {
////            if (slow != 0)
////            {
////                s[slow++] = ' ';
////            }
////            while (i < s.size() && s[i] != ' ')
////            {
////                s[slow++] = s[i++];
////            }
////        }
////    }
////    //for (int i = 0; i < s.size(); ++i)
////    //{
////    //    if (s[i] != ' ')
////    //    {
////    //        if (slow != 0)
////    //            s[slow++] = ' ';
////    //        while (i < s.size() && s[i] != ' ')
////    //        {
////    //            s[slow++] = s[i++];
////    //        }
////    //    }
////    //}
////    s.resize(slow); 
////}
////string reverseWords(string s)
////{
////    remove_space(s);
////    reverse(s.begin(), s.end());
////    int pos = 0;
////    int tmp = 0;
////    //反转单个字母
////    while (pos != string::npos)
////    {
////        pos = s.find(' ', pos + 1);
////        if (pos == string::npos)
////        {
////            reverse(s.begin() + tmp, s.end());
////        }
////        else
////        {
////            reverse(s.begin() + tmp, s.begin() + pos);
////        }
////        tmp = pos + 1;
////    }
////    return s;
////}
////class Solution {
////public:
////    vector<int> countBits(int n)
////    {
////        vector<int> ret;
////        for (int i = 0; i <= n; i++)
////        {
////            int count = 0;
////            while (i)
////            {
////                i = i & (i - 1);
////                count++;
////            }
////            ret.push_back(count);
////        }
////        return ret;
////    }
////
////};
//class Solution
//{
//    int tmp[50010];
//public:
//    int merge_sort(vector<int>& nums, int left, int right)
//    {
//        if (left >= right)
//        {
//            return 0;
//        }
//        int ret = 0;
//        int mid = (left + right) / 2;
//        ret += merge_sort(nums, left, mid);
//        ret += merge_sort(nums, mid + 1, right);
//
//        //计算翻转对 -- 升序 
//        int cur1 = left;
//        int cur2 = mid + 1;
//        while (cur2 <= right)
//        {
//            while (cur1 <= mid && nums[cur2] >= nums[cur1] / 2)
//            {
//                cur1++;
//            }
//            if (cur1 > mid)
//            {
//                break;
//            }
//            ret += mid - cur1 + 1;
//            cur2++;
//        }
//        //合并两个有序数组
//        cur1 = left;
//        cur2 = mid + 1;
//        int i = 0;
//        while (cur1 <= mid && cur2 <= right)
//        {
//            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
//        }
//        while (cur1 <= mid)
//        {
//            tmp[i++] = nums[cur1++];
//        }
//        while (cur2 <= right)
//        {
//            tmp[i++] = nums[cur2++];
//        }
//        for (int j = left; j <= right; j++)
//        {
//            nums[j] = tmp[j - left];
//        }
//        return ret;
//    }
//    int reversePairs(vector<int>& nums)
//    {
//        return merge_sort(nums, 0, nums.size() - 1);
//
//    }
//};
//int main()
//{
//    Solution s;
//    vector<int> v({ 1,3,2,3,1 });
//    s.reversePairs(v);
//
//	return 0;
//}
//
//
//
//
////
//////class A
//////{
//////public:
//////	A(int a = 1,int b = 2)
//////	{
//////		_a = a;
//////		_b = b;
//////	}
//////	~A()
//////	{
//////		;
//////	}
//////	int _a;
//////	int _b;
//////};
//////class Solution {
//////public:
//////    string multiply(string num1, string num2)
//////    {
//////
//////        if (num1 == "0" || num2 == "0")
//////        {
//////            return "0";
//////        }
//////        int end1 = num1.size() - 1;
//////        int end2 = num2.size() - 1;
//////        vector<int> v(end1 + end2 + 2);
//////
//////
//////        //从后往前遍历
//////        for (int i = 0; i <= end1; i++)
//////        {
//////            for (int j = 0; j <= end2; j++)
//////            {
//////                v[i + j] += ((num1[end1 - i] - '0') * (num2[end2 - j] - '0'));
//////            }
//////        }
//////        int carry = 0;
//////        for (int i = 0; i < v.size(); i++)
//////        {
//////            v[i] += carry;
//////            carry = v[i] / 10;
//////            v[i] %= 10;
//////        }
//////        string s;
//////        for (int i = v.size() - 1; i >= 0; i--)
//////        {
//////            if (i == v.size() - 1 && v[i] == 0)
//////            {
//////                continue;
//////            }
//////            s += (v[i] + '0');
//////
//////        }
//////        return s;
//////
//////    }
//////};
//////int main()
//////{
//////    Solution s;
//////    s.multiply("2","3");
//////}
//////
////
//////int main()
//////{
//////	int ar[] = { 1,2,3,4,0,5,6,7,8,9 };
//////	int n = sizeof(ar) / sizeof(int);
//////	vector<int> v(ar, ar + n);
//////	vector<int>::iterator it = v.begin();
//////	while (it != v.end())
//////	{
//////		if (*it != 0)
//////			cout << *it;
//////		else
//////			v.erase(it);
//////		it++;
//////	}
//////	return 0;
//////}
//////
////
////
////namespace bit
////{
////	void test_list1()
////	{
////		bit::list<int> lt;
////		lt.push_back(1);
////		lt.push_back(2);
////		lt.push_back(3);
////		lt.push_back(4);
////		const bit::list<int> lt2(lt);
////		list<int>::iterator it = lt2.begin();
////		while (it != lt2.end())
////		{
////			(*it)++;
////			cout << *it << " ";
////			++it;
////		}
////		cout << endl;
////	}
////}
////int main()
////{
////	bit::test_list1();
////
////	//test_op2();
////
////	return 0;
////}
//
////class Solution {
////public:
////    vector<vector<int>> levelOrder(TreeNode* root)
////    {
////        vector<vector<int>> vv;
////        queue<TreeNode*> q;
////        q.push(root);
////        int levelsize = 1;
////        while (!q.empty())
////        {
////            vector<int> v;
////            while (levelsize--)
////            {
////                TreeNode* tmp = q.front();
////                v.push_back(tmp->val);
////                q.pop();
////                if (tmp->left)
////                {
////                    q.push(tmp->left);
////                }
////                if (tmp->right)
////                {
////                    q.push(tmp->right);
////                }
////            }
////            levelsize = q.size();
////            vv.push_back(v);
////        }
////        return vv;
////    }
////};
